#include <stdio.h>
#include <stdlib.h>		/* for calloc() free() */

/* from <limits.h> for CHAR_BIT is 8 definition */
#define CHAR_BIT 8

/* min (x,y) spacing between nodes */
#define NXSPACING 5
#define NYSPACING 15

#include "sfg.h"

struct gml_graph;
struct gml_node;
struct gml_edge;
struct gml_nlist;
struct gml_elist;

struct gml_graph {
	int layouted;		/* set if layout is done */
	int nodenum;		/* highest node number in use */
	int nnodes;		/* number of nodes in the graph */
	int edgenum;		/* highest edge number in use */
	int nedges;		/* number of edges in the graph */
	int maxlevel;		/* maximum relative level */
	int nedgelabels;	/* number of edgelabels */
	int do_edgelabels;	/* if set add edgelabels in the graph */
	int nsinglenodes;	/* number of single nodes */
	int nhedges;		/* number of hor edges */
	int startnodeslevel;	/* level where graph drawing starts */
	int nstartnodes;	/* number of start node numbers */
	int *startnodes;	/* array with start node numbers */
	int xspacing;		/* min x spacing between nodes */
	int yspacing;		/* min y spacing between nodes */
	struct gml_nlist *nodelist;	/* list of nodes */
	struct gml_nlist *nodelistend;
	struct gml_nlist *singlenodelist;	/* list of single nodes */
	struct gml_nlist *singlenodelistend;
	struct gml_elist *edgelist;	/* list of edges */
	struct gml_elist *edgelistend;
	int *nnodes_of_level;	/* number of nodes for each level */
	int widestnnodes;	/* widest number of nodes on one level */
	int widestlevel;	/* widest level */
	int sugi_icrossings;	/* initial crossings */
	int sugi_fcrossings;	/* final crossings */
	int sugi_changes;	/* sugiyama changes made */
	int *numce;		/* number of crossings at every level */
	int *nume;		/* number of edges */
	int maxx;		/* max x pos of drawing */
	int maxy;		/* max y pos of drawing */
	int nodemin;		/* min. node number in use */
	int nodemax;		/* max. node number in use */
	int edgemin;		/* min. edge number in use */
	int edgemax;		/* max. edge number in use */
};

struct gml_node {
	int nr;			/* uniq node number */
	int tx;			/* text xsize */
	int ty;			/* text ysize */
	int bbx;		/* text xsize */
	int bby;		/* text ysize */
	int dummy;		/* set to 1 if dummy node */
	int elabel;		/* set if node is a edge label */
	int enumber;		/* orig. edge number of the edge label */
	int nselfedges;		/* number of self edges at this node */
	int done;		/* dfs black/white */
	int grey;		/* dfs grey */
	int indegree;		/* incoming edges to node */
	int outdegree;		/* outgoing edges from node */
	int hashedge;		/* set if node has hor. edge */
	void *data;		/* user data */
	int relx;		/* relative xpos */
	int rely;		/* relative ypos */
	int absx;		/* absolute xpos */
	int absy;		/* absolute ypos */
	int lx0;		/* absolute xpos */
	int ly0;		/* absolute xpos */
	int lx1;		/* absolute ypos */
	int ly1;		/* absolute ypos */
	int finx;		/* absolute xpos */
	int finy;		/* absolute ypos */
	struct gml_elist *outgoing_e;	/* source list, outgoing edges */
	struct gml_elist *outgoing_etail;	/* source list, outgoing edges */
	struct gml_elist *incoming_e;	/* target list, incoming edges */
	struct gml_elist *incoming_etail;	/* target list, incoming edges */
	int startnode;		/* node belongs to part of graph with this startnode */
	struct gml_node *el_fnode;	/* in edge-label the from-node */
	struct gml_node *el_tnode;	/* in edge-label the to-node */
};

struct gml_edge {
	int nr;			/* uniq edge number */
	struct gml_node *from_node;	/* from node */
	struct gml_node *to_node;	/* to node */
	int tx;			/* text xsize */
	int ty;			/* text ysize */
	int elabel;		/* set if there is a edge label */
	int reversed;		/* set if edge is reversed */
	int hedge;		/* set if hor. edge */
};

struct gml_nlist {
	struct gml_node *node;
	struct gml_nlist *next;
};

struct gml_elist {
	struct gml_edge *edge;
	struct gml_elist *next;
};

/* local vars */
static struct gml_graph *maingraph = NULL;

static struct gml_node *uniqnode(struct gml_graph *g, int nr);
static void uniqnode_add(struct gml_graph *g, struct gml_node *node);
static void clear_nodelist(struct gml_graph *g);
static void clear_edgelist(struct gml_graph *g);
static void prep(struct gml_graph *g);
static void reorg(struct gml_graph *g);
static void uncycle(struct gml_graph *g);
static void make_stlist(struct gml_graph *g);
static void clear_stlist(struct gml_node *node);
static void clear_stlist_all(struct gml_graph *g);
static void ylevels(struct gml_graph *g);
static void set_level2(struct gml_graph *g, struct gml_node *n, int i, int startnode);
static void shorteredges(struct gml_graph *g);
static void edgesdownwards(struct gml_graph *g);
static void edgelen(struct gml_graph *g);
static void doublespacey(struct gml_graph *g);
static void edgelabels(struct gml_graph *g);
static void splitedges(struct gml_graph *g);
static void nodecounts(struct gml_graph *g);
static void barycenter(struct gml_graph *g, int it1v, int it2v);
static void improve_positions(struct gml_graph *g);
static void finalxy(struct gml_graph *g);
static struct gml_edge *findedge(int num);
static void setminmax(struct gml_graph *g);
